/*
 * 4.4
 * Given a binary search tree, design an algorithm which creates a linked list of all the
 * nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <list>
#include <queue>
using namespace std;

typedef struct _tree_t {
    int value;
    struct _tree_t *left;
    struct _tree_t *right;
} tree_t;

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

list<list<tree_t *> > construct_list(tree_t *root)
{
    list<list<tree_t *> > lists;
    list<tree_t *> curr_list;
    queue<tree_t *> *curr_queue, *next_queue, q1, q2;
    curr_queue = &q1;
    next_queue = &q2;
    curr_queue->push(root);
    while (!curr_queue->empty()) {
        while (!curr_queue->empty()) {
            tree_t *t = curr_queue->front();
            curr_queue->pop();
            curr_list.push_back(t);
            if (t->left) {
                next_queue->push(t->left);
            }
            if (t->right) {
                next_queue->push(t->right);
            }
        }
        std::swap(curr_queue, next_queue);
        *next_queue = queue<tree_t *>();
        lists.push_back(curr_list);
        curr_list = list<tree_t *>();
    }
    return lists;
}

void free_tree(tree_t *root)
{
    if (!root) {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    tree_t *nodes[7];
    for (int i = 0; i < 7; i++) {
        nodes[i] = new_tree(i);
    }
    tree_t *root = nodes[0];
    root->left = nodes[1];
    root->right = nodes[2];
    nodes[1]->left = nodes[3];
    nodes[1]->right = nodes[4];
    nodes[4]->left = nodes[5];
    nodes[4]->right = nodes[6];
    list<list<tree_t *> > lists = construct_list(root);
    for (list<list<tree_t *> >::const_iterator it = lists.begin(); it != lists.end(); ++it) {
        for (list<tree_t *>::const_iterator it2 = it->begin(); it2 != it->end(); ++it2) {
            printf("%d ", (*it2)->value);
        }
        printf("\n");
    }
    free_tree(root);
    return 0;
}
